package explore.hxx.binarytree.self;

import explore.hxx.binarytree.dependence.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author waxijiang
 * # 路径总和问题
 * 题目来源
 * https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xo566j/
 */
public class PathSum {
    public static void main(String[] args) {
//        TreeNode root = new TreeNode(5);
//        root.left = new TreeNode(4);
//        root.right = new TreeNode(8);
//        root.left.left = new TreeNode(11);
//        root.left.right = null;
//        root.left.left.left = new TreeNode(7);
//        root.left.left.right = new TreeNode(2);
//        root.right.left = new TreeNode(13);
//        root.right.right = new TreeNode(4);
//        root.right.right.right = new TreeNode(1);
//        root.right.right.left = null;

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(-2);
//        root.right = new TreeNode(-3);
//        root.left.left = new TreeNode(1);
//        root.left.right = new TreeNode(3);
//        root.right.left = new TreeNode(-2);
//        root.right.right = null;
//        root.left.left.left = new TreeNode(-1);

        TreeNode root = new TreeNode(1);
        System.out.println(pathSum(root, 0));
    }

    public static boolean pathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        // 构造辅助堆栈
        Deque<TreeNode> stack = new LinkedList<>();
        Deque<Integer> crossroad = new LinkedList<>();
        stack.push(root);

        int tmpSum = 0;
        // 采用深度优先(DFS)遍历
        while (!stack.isEmpty()) {
            TreeNode tmpNode = stack.pop();
            tmpSum += tmpNode.val;
            // 存储交叉路口值
            if (tmpNode.left != null && tmpNode.right != null) {
                crossroad.push(tmpSum);
            }
            // 如果是叶子节点则检查路径长度是否等于sum
            if (tmpNode.left == null && tmpNode.right == null) {
                if (tmpSum == sum) {
                    return true;
                } else {
                    if (!crossroad.isEmpty()) {
                        tmpSum = crossroad.pop();
                    }
                    continue;
                }
            }

            // 否则继续遍历
            if (tmpNode.right != null) {
                stack.push(tmpNode.right);
            }
            if (tmpNode.left != null) {
                stack.push(tmpNode.left);
            }
        }
        return false;
    }
}
